#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
# http://www.careercup.com/question?id=5361917182869504
"""
a 32-bit integer could be splited into 32 small integers as: 
    1. bit 0~4 
    2. bit 1~5 
    ... 
    31. bit 30~31 and bit 0~2 
    32. bit 31 and bit 0~3 
    please find a 32-bit integer that could be splited into exactly 0~31 (the order doesn't matter).
"""
import os, re, sys, getopt
import logging
import locale
import copy
from utils import *


def search_append_zero(seed, head, tail, seem):
    target = (tail * 2 )% 32
    #print "==>target %s"%target
    if seem[target] == True: return seed
    else:
        new = copy.copy(seem)
        new[target] = True
        return search(seed + '0', head, target, new)

def search_append_one(seed, head, tail, seem):
    target = (tail * 2 + 1)% 32
    #print "==>target %s"%target
    if seem[target] == True: return seed
    else:
        new = copy.copy(seem)
        new[target] = True
        return search(seed + '1', head, target, new)

def search_prepend_zero(seed, head, tail, seem):
    target = (head / 2 )
    #print "==>target %s"%target
    if seem[target] == True: return seed
    else:
        new = copy.copy(seem)
        new[target] = True
        return search('0' + seed, target, tail, new)

def search_prepend_one(seed, head, tail, seem):
    target = (head / 2 + 16 )
    #print "==>target %s"%target
    if seem[target] == True: return seed
    else:
        new = copy.copy(seem)
        new[target] = True
        return search('1' + seed , target, tail, new)

def search(seed, head, tail, seem):
    """docstring for search"""
    #print seed
    if len(seed) == 36 and seed[:4] == seed[32:]: return seed
    new = search_append_zero(seed, head, tail, seem)
    if len(new) == 36 and new[:4] == new[32:]: return new 
    new = search_append_one(seed, head, tail, seem)
    if len(new) == 36 and new[:4] == new[32:]: return new 
    new = search_prepend_zero(seed, head, tail, seem)
    if len(new) == 36 and new[:4] == new[32:]: return new 
    new = search_prepend_one(seed, head, tail, seem)
    if len(new) == 36 and new[:4] == new[32:]: return new 
    return seed

@time_profile
def search_profile():
    seem = {}
    for i in xrange(0,32):
        seem[i] = False
    seem[0] = True
    return search("00000", 0, 0, seem)

def string_to_int(s):
    i = 0
    for k in xrange(0,len(s)):
        i *= 2
        if s[k] == '1': i = i+1
    return i

if __name__ == '__main__':
    result = search_profile()
    print result[:32]
    for i in xrange(0,32):
        print result[i:i+5],
        print "-->",
        print string_to_int(result[i:i+5])


